Grid Traversal Techniques (DFS, BFS)

Grid Traversal

Grid Traversal হল একটি টেকনিক যা কোনো 2D grid বা matrix-এর মধ্যে নোড (বা সেল) গুলি পরিদর্শন করার জন্য ব্যবহৃত হয়। এর মাধ্যমে বিভিন্ন সমস্যা যেমন ল্যাবিরিনথ ট্রাভার্সাল, শরণার্থী শিবিরের ম্যাপ, খোঁজার সমস্যা ইত্যাদি সমাধান করা যায়। সাধারণত এই ধরনের সমস্যা DFS (Depth First Search) এবং BFS (Breadth First Search) অ্যালগরিদম দিয়ে সমাধান করা হয়।

1. Depth First Search (DFS)

Depth First Search (DFS) একটি গ্রাফ বা গাছের মধ্যে একটি নির্দিষ্ট নোড থেকে শুরু করে যতটা সম্ভব গভীরে চলে যায়, তারপর পেছনে ফিরে এসে অন্য পথে চেষ্টা করে। এটি একটি রিকার্সিভ (recursive) অ্যালগরিদম এবং সাধারণত stack ডেটা স্ট্রাকচার ব্যবহার করে (যদিও এটি রিকার্সিভ হলে স্ট্যাক ব্যবহৃত হয় স্বাভাবিকভাবে)।

DFS-এ, আমরা একটি নোড থেকে শুরু করে যতটা সম্ভব গভীরে চলে যাই, তারপর অন্য একে একে সমস্ত নোড ভিজিট করি।

DFS Implementation (using Recursion):

import java.util.*;

public class DFS {
    private int rows, cols;
    private int[][] grid;
    
    // Direction arrays for moving up, down, left, right
    private int[] rowDir = {-1, 1, 0, 0};
    private int[] colDir = {0, 0, -1, 1};

    public DFS(int rows, int cols) {
        this.rows = rows;
        this.cols = cols;
        this.grid = new int[rows][cols];
    }

    // DFS helper function using recursion
    private void dfs(int row, int col, boolean[][] visited) {
        // Base condition to stop recursion
        if (row < 0 || col < 0 || row >= rows || col >= cols || grid[row][col] == 0 || visited[row][col]) {
            return;
        }

        // Mark current cell as visited
        visited[row][col] = true;

        // Visit all 4 adjacent cells (up, down, left, right)
        for (int i = 0; i < 4; i++) {
            int newRow = row + rowDir[i];
            int newCol = col + colDir[i];
            dfs(newRow, newCol, visited);
        }
    }

    // Function to traverse the grid using DFS
    public void gridTraversalDFS(int startRow, int startCol) {
        boolean[][] visited = new boolean[rows][cols];

        dfs(startRow, startCol, visited);

        System.out.println("DFS Traversal Complete");
    }

    public void printGrid() {
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                System.out.print(grid[i][j] + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        DFS dfs = new DFS(5, 5);
        
        // Creating a simple grid (1 for valid, 0 for invalid)
        int[][] grid = {
            {1, 1, 0, 1, 0},
            {1, 1, 0, 1, 1},
            {0, 1, 1, 0, 1},
            {1, 1, 0, 0, 0},
            {0, 1, 1, 1, 1}
        };
        
        // Initialize grid in DFS object
        dfs.grid = grid;

        // Starting DFS traversal from (0,0)
        dfs.gridTraversalDFS(0, 0);
    }
}

ব্যাখ্যা:

• DFS Traversal: এখানে আমরা একটি গ্রিডের মধ্যে DFS ব্যবহার করছি যেখানে শুধুমাত্র 1 এর সাথে সংযুক্ত সেলগুলি পরিদর্শন করা হচ্ছে। সেলগুলি যতটা সম্ভব গভীরে গিয়ে পরিদর্শন করা হয়, এবং তারপর পুনরায় অন্য সেলগুলিতে চেষ্টা করা হয়।
• Direction Arrays: rowDir এবং colDir এর মাধ্যমে আমরা উপরের, নিচের, বাম এবং ডান দিকে চলার জন্য চারটি দিকের মান পেয়েছি।
• Recursion: dfs() ফাংশনটি নিজেকে কল করে একে একে সমস্ত সেল পরিদর্শন করে।

2. Breadth First Search (BFS)

Breadth First Search (BFS) হল একটি গ্রাফ ট্রাভার্সাল অ্যালগরিদম যা সর্বপ্রথম নিকটবর্তী নোডগুলো পরিদর্শন করে এবং তারপর ধীরে ধীরে তাদের পাশের নোডগুলো পরিদর্শন করে। BFS queue ডেটা স্ট্রাকচার ব্যবহার করে, যা এটি প্রতিটি স্তরের সব নোডগুলো একে একে ভিজিট করতে সহায়ক।

BFS Implementation (using Queue):

import java.util.*;

public class BFS {
    private int rows, cols;
    private int[][] grid;

    // Direction arrays for moving up, down, left, right
    private int[] rowDir = {-1, 1, 0, 0};
    private int[] colDir = {0, 0, -1, 1};

    public BFS(int rows, int cols) {
        this.rows = rows;
        this.cols = cols;
        this.grid = new int[rows][cols];
    }

    // BFS helper function using queue
    private void bfs(int startRow, int startCol) {
        boolean[][] visited = new boolean[rows][cols];
        Queue<int[]> queue = new LinkedList<>();

        // Add the starting point to the queue
        queue.add(new int[]{startRow, startCol});
        visited[startRow][startCol] = true;

        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int row = cell[0];
            int col = cell[1];

            // Process the current cell
            System.out.println("Visiting cell: (" + row + ", " + col + ")");

            // Visit all 4 adjacent cells (up, down, left, right)
            for (int i = 0; i < 4; i++) {
                int newRow = row + rowDir[i];
                int newCol = col + colDir[i];

                // If the new cell is valid and not visited
                if (newRow >= 0 && newCol >= 0 && newRow < rows && newCol < cols && grid[newRow][newCol] == 1 && !visited[newRow][newCol]) {
                    queue.add(new int[]{newRow, newCol});
                    visited[newRow][newCol] = true;
                }
            }
        }
    }

    // Function to traverse the grid using BFS
    public void gridTraversalBFS(int startRow, int startCol) {
        bfs(startRow, startCol);
        System.out.println("BFS Traversal Complete");
    }

    public void printGrid() {
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                System.out.print(grid[i][j] + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        BFS bfs = new BFS(5, 5);

        // Creating a simple grid (1 for valid, 0 for invalid)
        int[][] grid = {
            {1, 1, 0, 1, 0},
            {1, 1, 0, 1, 1},
            {0, 1, 1, 0, 1},
            {1, 1, 0, 0, 0},
            {0, 1, 1, 1, 1}
        };

        // Initialize grid in BFS object
        bfs.grid = grid;

        // Starting BFS traversal from (0,0)
        bfs.gridTraversalBFS(0, 0);
    }
}

ব্যাখ্যা:

• BFS Traversal: এখানে BFS গ্রিডে সেলগুলো ভিজিট করতে ব্যবহৃত হচ্ছে। শুরুতে প্রথম সেলটি কিউতে যুক্ত করা হয় এবং কিউটি ফাঁকা না হওয়া পর্যন্ত প্রতিটি সেল পরিদর্শন করা হয়।
• Queue: BFS প্রক্রিয়াটি কিউ ডেটা স্ট্রাকচার ব্যবহার করে সেলগুলিকে স্তরের ভিত্তিতে পরিদর্শন করে।

3. DFS vs BFS

সারাংশ

Grid Traversal Techniques যেমন DFS (Depth First Search) এবং BFS (Breadth First Search) হল গ্রিডের মধ্যে সেলগুলোকে পরিদর্শন করার শক্তিশালী পদ্ধতি। DFS গভীরতার দিকে যেতে চায় এবং একে একে সমস্ত নোড বা সেল পরিদর্শন করে, যেখানে BFS স্তরভিত্তিক বা নিকটবর্তী নোডগুলো আগে পরিদর্শন করে। DFS সাধারণত রিকার্সন ব্যবহার করে এবং BFS কিউ ডেটা স্ট্রাকচার ব্যবহার করে। DFS এবং BFS উভয়ই গ্রিড ট্রাভার্সাল, ল্যাবিরিন্থ সমস্যা, shortest path সমস্যা ইত্যাদিতে ব্যবহৃত হয়।